package RBTree2;

import com.sun.org.apache.regexp.internal.REDebugCompiler;
import rbTree.Color;
import sun.reflect.generics.tree.Tree;

import java.io.Reader;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-04
 * Time: 9:02
 */
public class RBTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public Color color;

        public TreeNode(int val, Color color) {
            this.val = val;
            this.color = color;
        }

    }

    public TreeNode root;

    public void insert(int val) {
        TreeNode node = new TreeNode(val, Color.RED);
        if (root == null) {
            root = node;
            root.color = Color.BLACK;
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        if (parent.val < val) {
            parent.right = node;
            node.parent = parent;
        } else {
            parent.left = node;
            node.parent = parent;
        }
        cur = node;
        parent = cur.parent;
        while (parent != null && parent.color == Color.RED) {
            TreeNode grandParent = parent.parent;
            if (parent == grandParent.left) {
                TreeNode uncle = grandParent.right;
                if (uncle!=null && uncle.color == Color.RED) {
                    parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    grandParent.color = Color.RED;
                    cur = grandParent;
                    parent = cur.parent;
                } else {
                    //uncle.color == Color.BLACK,或者uncle不存在
                    if (cur == parent.right) {
                        rotateLeft(parent);
                        TreeNode tmp = cur;
                        cur = parent;
                        parent = tmp;
                    }
                    rotateRight(grandParent);
                    parent.color = Color.BLACK;
                    grandParent.color = Color.RED;


                }
            } else {
                //parent == grandParent.right
                TreeNode uncle = grandParent.left;
                if (uncle!=null && uncle.color == Color.RED) {
                    parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    grandParent.color = Color.RED;
                    cur = grandParent;
                    parent = cur.parent;
                } else {
                    //uncle.color == Color.BLACK,或者uncle不存在
                    if (cur == parent.left) {
                        rotateRight(parent);
                        TreeNode tmp = cur;
                        cur = parent;
                        parent = tmp;
                    }
                    rotateLeft(grandParent);
                    parent.color = Color.BLACK;
                    grandParent.color = Color.RED;
                }
            }
            root.color = Color.BLACK;
        }

    }

    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        subR.left = parent;
        parent.right = subRL;
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if (subRL != null) {
            subRL.parent = parent;
        }
        if (parent == root) {
            root = subR;
            subR.parent = null;
        } else if (pParent.left == parent) {
            pParent.left = subR;
            subR.parent = pParent;
        } else {
            pParent.right = subR;
            subR.parent = pParent;
        }
    }

    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        subL.right = parent;
        parent.left = subLR;
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        if (subLR != null) {
            subLR.parent = parent;

        }
        if (parent == root) {
            root = subL;
            subL.parent = null;
        } else if (pParent.left == parent) {
            pParent.left = subL;
            subL.parent = pParent;
        } else {
            pParent.right = subL;
            subL.parent = pParent;
        }
    }

    public boolean isRBTree() {
        if (root == null) {
            return true;
        }
        if (root.color != Color.BLACK) {
            System.out.println("根结点不是黑色的!");
            return false;
        }
        int blackNum = 0;
        TreeNode cur = root;
        while(cur!=null){
            if(cur.color ==Color.BLACK){
                blackNum++;
            }
            cur = cur.left;
        }

     return checkBlackNum(root , 0,blackNum) && checkColorRed(root);

    }

    private boolean checkColorRed(TreeNode root) {
        if(root == null){
            return true;
        }
        TreeNode cur =root;

        if(cur.color == Color.RED){
            TreeNode parent = root.parent;
            if(parent.color ==Color.RED){
                System.out.println("出现了两个连续的红色节点!");
                return false;
            }

        }
        return checkColorRed(root.left) && checkColorRed(root.right);
    }


    public boolean checkBlackNum(TreeNode root, int pathBlackNum , int blackNum){
        if(root == null){
            return true;
        }
        if(root.color == Color.BLACK){
            pathBlackNum++;
        }
        if(root.left==null && root.right ==null){
            if(pathBlackNum != blackNum){
                return false;
            }
        }
        return checkBlackNum(root.left,pathBlackNum,blackNum) &&
                checkBlackNum(root.right , pathBlackNum ,blackNum);

    }


    public static void main(String[] args) {

    }
}
